package org.example.BinaryTree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Set;

public class Mode_in_binary_search_trees {
    public static HashMap<Integer, Integer> map = new HashMap<>();
    public static TreeNode pre;

    public static void main(String[] args) {
        //二叉搜索树中的众数

        //给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
        //如果树中有不止一个众数，可以按 任意顺序 返回。
        //假定 BST 满足如下定义：
        //结点左子树中所含节点的值 小于等于 当前节点的值
        //结点右子树中所含节点的值 大于等于 当前节点的值
        //左子树和右子树都是二叉搜索树

        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(7);
        TreeNode node3 = new TreeNode(2);
        TreeNode node4 = new TreeNode(3);
        TreeNode root = new TreeNode(4);
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        int[] arr = findMode(root);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }

    public static int[] findMode(TreeNode root) {
        get(root);
        int max = Integer.MIN_VALUE;
        ArrayList<Integer> result = new ArrayList<>();
        Set<Integer> keySet = map.keySet();
        for (Integer key : keySet) {
            Integer times = map.get(key);
            if (times > max) max = times;
        }
        for (Integer key : keySet) {
            Integer times = map.get(key);
            if (times == max) result.add(key);
        }
        return result.stream().mapToInt(i->i).toArray();
    }

    public static void get(TreeNode root) {
        if (root == null) return;
        get(root.left);
        if (pre != null && pre.val == root.val) {
            Integer times = map.get(pre.val);
            times += 1;
            map.put(pre.val, times);
        } else {
            pre = root;
            map.put(pre.val, 1);
        }
        get(root.right);
    }
}
